Asymptotic Notation

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

(Order of Growth): Describing limiting behavior.

◇Key Concepts

Purpose Notations ◇Big-O Notation (O) ◇Big-Omega Notation (Ω) ◇Big-Theta Notation (Θ)

◇Details / Theory

(◇Order of Growth): Describing limiting behavior. - Purpose: To describe the algorithm's efficiency (◇Running Time, ◇Space Complexity) as the input size (n) approaches infinity, ignoring constant factors and lower-order terms. Characterizes the rate of growth. (Handout 03, Page 2) - Notations: - ◇Big-O Notation (O) - ◇Big-Omega Notation (Ω) - ◇Big-Theta Notation (Θ) - ◇Little-o Notation (o) Not included in Exam - ◇Little-omega Notation (ω) Not included in Exam - Properties: Transitivity, Reflexivity (for O, Ω, Θ), Symmetry (for Θ), Transpose Symmetry (O vs Ω, o vs ω). - Common ◇Growth Rates (Slowest to Fastest): (Handout 03, Page 17) - Θ(1): Constant (e.g., accessing an array element) - Θ(log n): Logarithmic (e.g., binary search) - Θ(n): Linear (e.g., finding max in an unsorted array) - Θ(n log n): Linearithmic (e.g., efficient sorting like Merge Sort, Heap Sort) - Θ(n²): Quadratic (e.g., simple sorting like Bubble Sort, checking all pairs) - Θ(n³): Cubic (e.g., basic matrix multiplication) - Θ(2ⁿ), Θ(kⁿ): Exponential (e.g., finding all subsets, some brute-force algorithms) - Θ(n!): Factorial (e.g., generating all permutations) - Practical Significance: Helps choose algorithms that scale well for large inputs. An algorithm with lower asymptotic complexity will eventually outperform one with higher complexity, regardless of constant factors, for sufficiently large n.

◇Complexity

◇Common Pitfalls

Using Big-O when a tight bound ($\Theta$) is known and more informative. Thinking asymptotic notation tells you which algorithm is faster for small inputs — it only applies as $n \to \infty$.

◇Summary

TL;DR — Asymptotic notation (O, Ω, Θ, o, ω) describes how running time/space grows as $n \to \infty$, ignoring constants and lower-order terms. Common growth rates range from constant $O(1)$ to factorial $O(n!)$.

◇Links

Related: - ◇Order of Growth - ◇Running Time - ◇Space Complexity - ◇Big-O Notation - ◇Big-Omega Notation - ◇Big-Theta Notation - ◇Little-o Notation - ◇Little-omega Notation - ◇Growth Rates Source / Reference:

◇References & Navigation

• Previous Topic: ◇Assignment - Read - Write
• Next Topic: ◇Average-Case Analysis
• Related Notes: ◇Big-O Notation, ◇Order of Growth